
1. Field of the Invention
The present invention relates in general to computer-aided design tools for analyzing integrated circuit (IC) designs and in particular to a method and apparatus for estimating the capacitance of signal paths within an IC.

2. Description of Related Art
An IC designer typically generates a hardware description language (HDL) netlist describing an IC as a set of cells interconnected by signal paths (nets). Each cell produces one or more output signals in response to input signals with the input and output signals arriving and departing on the nets. The HDL netlist typically describes each cell only in terms of logical relationships between its input and output signals. After creating a netlist, the designer uses synthesis tools to convert the HDL netlist into a gate level netlist describing the cells in terms of logic gates or other structures that are to be incorporated into the IC to implement cell logic. The gate level netlist indirectly describes each cell by referring to an entry for that cell in a cell library, a database including a separate entry for each type of cell that can be incorporated into an IC. The cell library entry for each cell provides information about the cell including names of its input and output terminals, behavioral models of the cell, and a description of the cell layout.
After using a synthesis tool to generate a gate level netlist, the designer typically uses a placement and routing tool to generate an IC layout file indicating the position of each cell within the IC and indicating how the nets interconnecting the cells are to be formed. The nets include conductors formed on one or more layers of the IC and may include buffers for amplifying signals as they travel between cells.
Most digital ICs employ register transfer logic wherein each cell includes an output register, clocked by a leading or trailing edge of a clock signal, for storing one or more bits, each representing a state of one of the cell's output signals. The bits stored in that cell's output register control the state of the cell's output signals during the next clock cycle. Suppose a cell A stores a bit in its output register on the leading edge of a clock signal for controlling an output signal supplied through a net as an input signal to another cell B. Suppose also that cell B is to store a bit in its output register on the leading edge of the clock signal that is a function of the state of its input signal from cell A. Then after an edge of the clock signal changes a state of a bit stored in the output register of cell A, a cell A output signal edge must travel via a net to the cell B input, and cell B must process that signal edge and change the state of a bit supplied to its output register before the next leading edge of the clock signal.
For the IC to operate properly, the total signal path delay between the output register of cell A and the output register of cell B must be no longer than one clock signal cycle. Since the cell library will typically indicate the amount of time cell B requires to respond to a state change in its input signal (the cell's delay), a timing analysis tool can determine that net connecting cell A to cell B must have a path delay no longer than the difference between one clock signal cycle and the cell's delay. A designer establishes a timing budget indicating the maximum allowable delay through seconds of any time constrained signal path, and after using a placement and routing tool to generate an IC layout file, a designer will employ a timing analysis tool to check the layout to determine whether timing constraints on all signal paths have been satisfied.
In a typical IC, the nets are formed in part by conductors residing on layers of insulating material above the semiconductor substrate and by conductive vias passing vertically through the insulation layers for interconnecting conductors on different layers to one another and to transistors or other structures formed in the substrate. A net may also include buffers cells formed in the substrate. The path delay between any two terminals of IC devices connected though a net is therefore the sum of delays through the conductors, vias and buffers that conveying signals between those two terminals.
For a timing analysis tool to determine whether a signal path satisfies a timing constraint, it is necessary to be able to accurately estimate the path delay through each portion of the signal path. The path delay through a conductor forming a part of a signal path is largely a function of its shunt capacitance and its series resistance. As a signal edge propagates along the conductor, it has to charge or discharge the shunt capacitance it encounters before it can continue onward, and the time it requires to do that is a function of the magnitudes of the conductor's shunt capacitance and series resistance. Since the effects on path delay of conductor inductance is typically small, the conductor's inductance is usually ignored. Therefore to enable a timing analysis tool to estimate path delays through signal paths within an IC, a designer will first employ a resistance/capacitance (RC) extraction tool to estimate the resistance and capacitance of the conductors forming parts of those signal paths. The designer will then employ a timing analysis tool to estimate the path delay though each signal path as a function of the resistance and capacitance of conductors and of other component parts of the signal path.
A typical P&R tool generates an IC layout in the form of a data file which, among other things, specifies dimensions of each conductor forming a part of a net. The resistance per unit length of a conductor is a function of its cross-sectional area and the resistivity of the material forming the conductor. An RC capacitance tool searches through the IC layout file to locate the description of each conductor, ascertains the dimensions of the conductor from it description, and then estimates the conductor's resistance based on its dimensions.
The notion of “capacitance” relates to the amount of charge two conductors can store in an electric field between them when they are at different voltages, and the capacitance between any two conductors is a function of the size, shape and relative position and orientation of the two conductors and of the dielectric constant of the insulating material in which the field resides. The capacitance of any conductor of an IC is the sum of the capacitance between that conductor and every other conductor everywhere. However since the capacitance between two widely separated conductors is very small, an RC extraction tool can accurately estimate the capacitance of any conductor in an IC as the sum of the capacitances between that conductor and only its nearest neighbor conductors. The contributions to a conductor's capacitance from more distant conductors are ignored as being insignificant.
Since the capacitance of a conductor in an IC is a function not only of that conductor's dimensions, but also a function of the dimension and relative positioning and orientation of nearby conductors, estimating the capacitance of each conductor can be somewhat more complicated and time-consuming than estimating its resistance. A typical prior art RC extraction tool searches an IC layout file to locate a reference to a conductor and determine its dimensions and position in the layout. The RC extraction tool then searches the IC layout file again to determine the dimensions and relative position of every other conductor sufficiently close to that conductor to substantially influence its capacitance. The tool then computes the capacitance between that conductor and those nearby conductors. Thus a conventional RC extraction tool may have to search the IC layout file once for each conductor in the IC to find all conductors near it. Searching an IC layout file can be time-consuming for a computer programmed to function as an RC extraction tool particularly when the file is too large to reside wholly in the computer's random access memory (RAM). In that case the computer will have to access a hard disk containing the file many times to read successive portions of the file into RAM and separately search each portion of the file. Since disk accesses are time-consuming, much of the time a typical RC extraction tool needs to estimate conductor capacitance can be spent reading data from a hard disk.
What is needed is a method for accurate estimating capacitances of conductors in an IC layout that substantially reduces the number times an RC extraction tool must access a hard disk when the layout file is too large to reside wholly in RAM.